package UnionFind;

import java.util.*;

public class _128_LongestConsecutiveSequence {
    public int longestConsecutive_1(int[] nums) {
        if(nums.length<2) return nums.length;
        Arrays.sort(nums);
        int max = 0;
        int count =1;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i + 1] == nums[i] + 1) {
                count++;
            } else if (nums[i + 1] == nums[i]) {
                continue;
            } else {
                if (count > max) {
                    max = count;
                }
                count = 1;
            }
        }
        if (count > max) {
            max = count;
        }
        return max;
    }

    //solution 2:union find
    Map<Integer,Integer> ids;
    Map<Integer, Integer> count;
    public int longestConsecutive(int[] nums) {
        if(nums.length<2) return nums.length;
        Set<Integer> seqs = new HashSet<>();
        this.ids = new HashMap<>();
        this.count = new HashMap<>();
        for (int num : nums) {
            ids.put(num, num);
            count.put(num, 1);
            seqs.add(num);
        }
        for (int num : nums) {
            if (seqs.contains(num - 1)) {
                union(num - 1, num);
            }
        }
        int max = 0;
        for (Map.Entry<Integer, Integer> e : count.entrySet()) {
            max = Math.max(e.getValue(), max);
        }
        return max;
    }

    public int find(int q) {
        while (ids.get(q)!=q) {
            q = ids.get(q);
        }
        return q;
    }

    public void union(int p, int q) {
        int pid = find(p);
        int qid = find(q);
        if(pid==qid) return;
        ids.put(qid, pid);
        count.put(pid, count.get(qid) + count.get(pid));
    }
}
